/*--- HashPJW ----------------------------- Listing 3-2 ---------
 *	An adaptation of Peter Weinberger's (PJW) generic hashing
 *  algorithm based on Allen Holub's version.
 *
 *  Accepts a pointer to a datum to be hashed and returns an
 *  unsigned integer. This integer is called "calculated-key"
 *  in the text.
 *-------------------------------------------------------------*/

#include <limits.h>

/* corrected per comments in notes.txt
 * #define BITS_IN_int ((UINT_MAX + 1) / (UCHAR_MAX + 1)) / CHAR_BIT
 */
#define BITS_IN_int     (sizeof(int) * CHAR_BIT )
#define THREE_QUARTERS	((int)((BITS_IN_int * 3) / 4))
#define ONE_EIGHTH		((int)(BITS_IN_int / 8))
#define HIGH_BITS		( ~((unsigned int)(~0) >> ONE_EIGHTH))

unsigned int HashPJW(const char *datum)
{
	unsigned int hash_value, i;

	for (hash_value = 0; *datum; ++datum) {
		hash_value = (hash_value << ONE_EIGHTH) + *datum;
        if ((i = hash_value & HIGH_BITS) != 0)
			hash_value = (hash_value ^ (i >> THREE_QUARTERS)) & ~HIGH_BITS;

	return (hash_value);
}
